package algorthm.systemTraning.greedyAlgorithm;


import com.sun.xml.internal.ws.util.StringUtils;
import org.apache.commons.io.FileUtils;

import java.io.File;
import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.util.*;

/**
 * @className: huffman编码解决的是使用最小内存大小保存一个文本。
 * @Description:
 * @Author: wangyifei
 * @Date: 2024/4/15 22:29
 */
public class Huffman {

    public static void main(String[] args) throws IOException {
//        huffman编码解决的是使用最小内存大小保存一个文本
        // 如何将下面的英文进行压缩。
        String cnt = "Visitors at the fourth China International Consumer Products Expo can experience cutting-edge technology with a variety of interactive experiences.";
//        cnt += "The Table API is a declarative DSL centered around tables, which may be dynamically changing tables (when representing streams). The Table API follows the (extended) relational model: Tables have a schema attached (similar to tables in relational databases) and the API offers comparable operations, such as select, project, join, group-by, aggregate, etc. Table API programs declaratively define what logical operation should be done rather than specifying exactly how the code for the operation looks. Though the Table API is extensible by various types of user-defined functions, it is less expressive than the Core APIs, and more concise to use (less code to write). In addition, Table API programs also go through an optimizer that applies optimization rules before execution.";
//        cnt += "The Hands-on Training explains the basic concepts of stateful and timely stream processing that underlie Flink’s APIs, and provides examples of how these mechanisms are used in applications. Stateful stream processing is introduced in the context of Data Pipelines & ETL and is further developed in the section on Fault Tolerance. Timely stream processing is introduced in the section on Streaming Analytics.";
        cnt = FileUtils.readFileToString(new File("D:/words.txt"), StandardCharsets.UTF_8);
        char[] chars = cnt.toCharArray();
        Map<Character , Integer> cha = new HashMap<>();
        for (char aChar : chars) {
            cha.computeIfPresent(aChar , (key , oldValue)->{
                return oldValue + 1;
            });
            cha.computeIfAbsent(aChar, x -> {
                return 1;
            });
        }
        System.out.println("在 assic 码中，有 " + cha.size() + "字符");
        // 所以可以用 2 的 5 次方来计算，也就是 5 位的二进制来标识。
        Map<Character,Integer> mapping = new HashMap<>();
        Iterator<Map.Entry<Character, Integer>> iterator = cha.entrySet().iterator();
        int flag = 0 ;
        while (iterator.hasNext()) {
            Map.Entry<Character, Integer> next = iterator.next();
            mapping.put(next.getKey() , flag++);
            System.out.println("character: " + next.getKey() + " , value:" + next.getValue());
        }
        mapping.forEach((k,v)->{
            System.out.println("charater: "
                    + k + " , decode: " + pad(Integer.toBinaryString(v) , "0" , 5));
        });
        PriorityQueue<Node> nodes = new PriorityQueue<>(mapping.size());
        cha.forEach((key , value) -> {
            nodes.add(new Node(key , null , null , value));
        });
        Node head = huffmanTree(nodes);
        Map<Character, String> characterIntegerMap = huffmanCode(head);
        int sum = 0 ;
        Iterator<Map.Entry<Character, String>> iterator1 = characterIntegerMap.entrySet().iterator();
        int max = maxRadix(mapping.size());
        int s = 0 ;
        while (iterator1.hasNext()) {
            Map.Entry<Character, String> next = iterator1.next();
            System.out.println("character: " + next.getKey() + " code: " + next.getValue());
            int count = (int)cha.get(next.getKey());
            sum += ( count * next.getValue().length());
            s += max * count;
        }
        System.out.println("如果 huffman 编码的话，一共需要 " + sum + " bit 才能保存");
        System.out.println("如果使用固定长度的 bit 位表示的话，一共需要 " + s + " bit 才能保存");
    }
    public static PriorityQueue<Node> getQueue(String input){
        Map<Character , Integer> cha = new HashMap<>();
        for (char c : input.toCharArray()) {
                cha.computeIfPresent(c , (key , oldValue)->{
                    return oldValue + 1;
                });
                cha.computeIfAbsent(c , x -> {
                    return 1;
                });
        }
        PriorityQueue<Node> nodes = new PriorityQueue<>(cha.size());
        cha.forEach((key , value) -> {
            nodes.add(new Node(key , null , null , value));
        });
        return nodes ;
    }
    public static int maxRadix(int num){
        int i = 0 ;

        while(num > (1<<i) - 1){
            i++;
        }
        return i ;
    }
    public static int setBit(int target , int w , int value){
        int i = (1 << w);
        return value == 0 ? (target & ~i) : ( target | i);
    }
    public static int maxLevel = 0;
    public static Map<Character , String> huffmanCode(Node head){
        Map<Character , String> rs = new HashMap<>();
//        process(head , 0 , 0 , 0, rs);
        maxLevel = process2(head, "", 0, rs);
        return rs ;
    }
    public static int process2(Node head , String binaryStr , int value , Map<Character , String> map){
        if(head.c != null){
           map.put(head.c ,  binaryStr + value);
           int p = 1 + binaryStr.length();
           return p;
        }
        int p1 = process2(head.left ,  binaryStr + "1" , 1 , map);
        int p2 = process2(head.right ,  binaryStr + "0" , 0 , map);
        return Math.max(p1 , p2);
    }
    public static void process(Node head , int level , int i ,int value , Map<Character , Integer> map){
        if(head.c != null){
           map.put(head.c , setBit(i , level , value));
           return;
        }
        process(head.left , level + 1 , setBit(i , level , 1) , 1 , map);
        process(head.right , level + 1 , setBit(i , level , 0) , 0 , map);
    }

    public static Node huffmanTree(PriorityQueue<Node> queue){
        Node head = null ;
        Node first = null ;
        Node second = null ;
        Node h =  null ;
        while(!queue.isEmpty()){
            first = queue.poll();
            second = queue.poll();
            if(null == second){
                break ;
            }
            h = new Node(null , first , second , first.weight + second.weight);
            head = h ;
            queue.add(h);
        }
        return head ;
    }
    public static class Node implements Comparable<Node>{
        public Node left ;
        public Node right ;
        public int weight ;
        public Character c ;
        public Node(Character c , Node l , Node r , int w){
            left = l ;
            right = r ;
            weight = w ;
            this.c = c ;
        }

        @Override
        public int compareTo(Node o) {
            return this.weight - o.weight;
        }
    }
    public static String pad(String input , String word , int total){
        if(input.length() < total) {
            return repeat(word , total - input.length()).concat(input);
        }
        return input.substring(input.length() - total) ;
    }
    public static String repeat(String input , int n){
        String rs = "";
        for(int i = 0 ; i < n ; i++){
            rs += input ;
        }
        return rs ;
    }
}
